Many search engine services, such as Google and Overture, provide for searching for information that is accessible via the Internet. These search engine services allow users to search for display pages, such as web pages, that may be of interest to users. After a user submits a search request that includes search terms, the search engine service identifies web pages that may be related to those search terms. To quickly identify related web pages, the search engine services may maintain a mapping of keywords to web pages. This mapping may be generated by “crawling” the web (i.e., the World Wide Web) to identify the keywords of each web page. To crawl the web, a search engine service may use a list of root web pages to identify all web pages that are accessible through those root web pages. The keywords of any particular web page can be identified using various well-known information retrieval techniques, such as identifying the words of a headline, the words supplied in the metadata of the web page, the words that are highlighted, and so on. The search engine service may generate a relevance score to indicate how relevant the information of the web page may be to the search request based on the closeness of each match, web page importance or popularity (e.g., Google's PageRank), and so on. The search engine service then displays to the user links to those web pages in an order that is based on their rankings.
Many different page rank algorithms have been used to calculate the importance or page rank of web pages. Many of these algorithms are variations of the PageRank algorithm proposed by S. Brin, L. Page, R Motwami, and T. Winograd in “The PageRank Citation Ranking: Bringing Order to the Web,” Stanford University Technical Report, 1998. These algorithms calculate the importance of web pages based on links between web pages using the assumption that web pages typically include links to important web pages. Thus, a web page that is linked to by many web pages is likely to be an important web page. These algorithms represent the links between web pages using an adjacency matrix that indicates which web pages have links to which other web pages. The adjacency matrix A[i,j] is set to 1 when web page i has a link to web page j, and 0 otherwise. These algorithms are generally recursive and are variations of following:
                              PR          i                =                              (                          1              -              w                        )                    +                      w            ⁢                                          ∑                j                            ⁢                                                PR                  j                                                  C                  j                                                                                        (        1        )            where PRi is the page rank of web page i, web page j has a link to web page i, Cj is the number of links on web page j, and w is a weight factor. To calculate the importance of a web page using these algorithms, the importance of every web page is simultaneously calculated. The computational complexity of these page rank algorithms is generally O(n2). As a result, it is very time-consuming to calculate importance when the corpus of web pages is very large. It would be desirable to have a page rank algorithm that would allow for more rapid calculation of importance while maintaining a similar ranking among the pages.